Javed M A, Younis M S, Latif S, et al. Community detection in networks: A multidisciplinary review[J]. Journal of Network and Computer Applications, 2018, 108: 87-111.
一、背景介绍
文章首先指出了社区（community）结构是网络结构数据的典型特征，并且给出了一个定义：Community or cluster is defined as a group of nodes having similar affiliations different to rest of the network (Yang et al., 2010). 其次，作者给出了社区发现（community detection）的工作目标：Community detection refers to the procedure of identifying groups of interacting vertices (i.e., nodes) in a network depending upon their structural properties (Kelley et al., 2012; Yang et al., 2013). 接着，作者列举了在静态网络（static network）和动态网络（dynamic network）中一些已有的社区发现算法，例如谱聚类（spectral clustering）、模块度最大化（modularity maximization）等。然而，这些方法主要是用来识别网络中的不重叠社区（disjointed community），即一个节点仅属于一个社区。对于一个节点属于多个社区的情况，需要用到重叠社区发现算法。 作者指出，对社区发现算法进行评估也很重要。对这些算法的相对性能进行比较的最佳方法是在已知社区结构的复杂网络上根据一些指标进行测试。此外，文章提到在大规模网络中，社区发现非常有用，很多应用使用社区发现算法来揭示网络中隐藏的结构。 最后，作者指出了本文工作的特殊贡献：
由于该文章是综述类文献，因此回顾的论文数量较多，几乎覆盖了社区发现领域的所有算法。我们先看作者在论文中给出的图2，对于最基本的分类有一个初步的了解。 可以看到，作者将社区发现算法分成两大类，第一类是非重叠社区（每一个节点只属于一个社区）的社区发现算法，第二类是重叠社区（一个节点可以属于多个社区）的社区发现算法。目前大部分的社区发现算法属于第一类，又被细分成传统算法、基于模块度（modularity）的算法以及动态算法。 针对每一个分类，作者给出了经典的文章及应用，并且总结了相应算法的优点、缺点等，这些都被详细列在文章的表2当中。这里截取一部分进行展示。我们在此处为大家延伸8个算法的内容，这8个算法在R语言中有成熟的R包可以调用，方便入门者熟悉社区发现算法。 此处参考另外1篇对比这8个算法的文章：Yang Z, Algesheimer R, Tessone C J. A comparative analysis of community detection algorithms on artificial networks[J]. Scientific Reports, 2016, 6(1): 1-18. 这8个算法分别是：
1.Edge-betweenness
这是Newman and Girvan (2004)提出的一种用于社区发现的算法，发表于PNAS。这两位作者在社区发现领域发表了许多文章，引用量极高，做出了很大的贡献。Edge-betweenness算法的核心想法是对于网络中的每一条边计算一个edge-betweenness centrality指标，然后按照edge-betweenness centrality从大到小不断删掉这些边，每次删掉一条边都要重新计算这个指标。这样一来就能形成一种类似层次聚类的效果，产生一个自上而下的树，实现社区发现。 Edge-betweenness算法的思想非常直观，效果也很好，只不过在计算速度上差强人意，其计算复杂度是O(m^2 n)，其中m是网络中边的数量，n是网络中节点的个数。
图片来源：Girvan and Newman (2002)
2.Fastgreedy
这是Clauset et al. (2004)提出的一种基于模块度的社区发现算法。该算法与Newman (2004)所采用的贪婪优化算法相同，因此给出的结果也相同。（注：部分网友将Newman (2004)提出的方法称为fastgreedy算法，在此我们以igraph包中cluster_fast_greedy函数所实现的Clauset et al. (2004)方法为准。）Newman (2004)提出的贪婪优化算法首先将网络中的每个节点都作为一个单独社区，然后选出使得模块度增值最大的社区对进行合并。如果网络中的所有节点属于同一个社区，则停止合并过程。最终我们得到一个自下而上的树，树的每一层切分对应着网络的某个具体划分。该算法的计算复杂度是O((m+n)n)。Clauset et al. (2004)利用稀疏邻接矩阵的数据结构，进一步提高了Newman (2004)算法的速度，算法复杂度降低为O(mdlogn)，其中d是树的深度。该算法可以分析有数百万个节点和数千万条边的大型网络。
该算法是Rosvall and Bergstrom (2008)和Rosvall et al. (2009)提出的基于信息理论原理的社区发现算法。该方法通过最优地压缩网络上信息流的描述，将网络分解为多个模块。
5.Label propagation
这是Raghavan et al. (2007)提出的一种快速、近线性时间的社区发现算法。该算法首先给每个节点指定唯一的标签，然后每个节点以同步方式获取其邻居的最频繁标签并将标签重新分配给节点。迭代更新节点标签，当每个节点的标签是其附近最频繁的标签之一时，该方法停止。
6.Multilevel
这是Blondel et al. (2008)提出的一种基于模块度度量的分层社区发现算法。最初，每个节点都单独作为一个社区。在每一步中，节点都以局部的、贪婪的方式重新分配给社区：每个节点都移动到对模块度提升最大的社区中。当没有节点可以重新分配时，每个社区被认为是一个单独的节点，重复上述过程。当只剩下一个节点，或者模块度不能在一个步骤中再增加时，该算法停止。
7.Walktrap
这是Pons and Latapy (2005)提出的一种基于随机游动的社区发现方法。该算法的主要思想是在网络中进行随机游走，游走更有可能停留在同一社区内，因为只有少数几条边通向社区之外。
8.Spinglass
这是Reichardt and Bornholdt (2006)和Traag and Bruggeman (2009)提出的一种社区发现方法。该算法扩展了现有的Potts模型，以检测同时存在正向和负向链接的复杂网络中的社区。该方法解决了社会平衡理论中长期存在的一个问题，即带符号网络的聚类问题。大家可以加载R语言的igraph包，通过这些函数实现以上的算法：cluster_edge_betweenness，cluster_fast_greedy，cluster_leading_eigen，cluster_infomap， cluster_label_prop，cluster_louvain，cluster_walktrap，cluster_spinglass
三、算法的比较
我们回到这篇综述性的文章上来，接下来给大家介绍一下比较不同的社区发现算法的标准数据集和指标。
1.数据集
数据集一方面有模拟生成的标准数据集。Aldecoa and Marin (2012)将其分为两类，分别是开放式和封闭式。开放式标准数据集是由一个已知社区结构的网络通过节点之间随机重连，不同社区节点之间的连接增加，从而使网络成为一个开放式的未知网络结构。常见的开放式标准数据集有GN标准数据集、LFR标准数据集和RC标准数据集。封闭式标准数据集也是从已知社区结构的网络开始，但与开放式标准数据集相比，这里的节点重连不是随机的。最终得到的网络与初始网络具有相同的社区结构，但节点在社区中随机重新分配，具体细节可参考Aldecoa and Marin (2012)。另一方面，作者也提供了一些实际数据，如文中表3所列。
2.指标
为了评估社区发现效果的好坏，需要将算法划分的社区与参考社区进行比较，常用的指标有centrality metrics (Betweenness Centrality (BC)、Closeness centrality (CC)、Degree centrality (DC))、Fraction of Correctly Classified nodes (FCC)、The Rand Index (RI)、Adjusted RI (ARI)和Normalized Mutual Information measure (NMI)。其中RI指标是两个社区中一致的节点对的比例，RI为0代表该社区发现算法没能成功估计出社区结构，RI为1代表该社区发现算法能够精确地估计出社区结构。NMI指标是在经典聚类背景下定义的，通过测量一个数据集的两个不同划分的互信息量，从而度量两个社区划分的相近程度。NMI的值域是0到1，越高代表划分得越准。 当然，除了关注社区发现算法划分的准确度，我们还需要评估算法本身的性能，即实现某一算法的计算成本和主存储器的消耗。文中表6展示了不同算法的计算成本。
四、社区发现的应用
文章还介绍了社区发现算法在不同领域的潜在应用，例如在在线社交网络（online social networks）、通信网络（communication networks）、电子商务（E-Commerce）、学术界和科学计量学（academia and scientometrics）、生物系统和医疗保健（biological systems and healthcare）和经济学（economics）等领域。社区发现除了在上述领域有应用外，在识别重要的隐藏网络的社区结构方面还有着广泛的应用，例如诈骗识别（fraud detection）、链路预测（link prediction）、重构软件包（refactoring software packages）及网络中的异常检测（anomaly detection in networks）等。
五、社区发现算法面临的问题
文章最后总结了社区发现算法面临的主要问题：
混合类型数据的聚类（混合类型数据是指同时包含数值属性和类别属性的数据集）；
对不同算法社区发现质量的评估；
合并二分网络的信息；
实时数据集的可用性等。
参考文献
[1]Aldecoa R, Marin I. Closed benchmarks for network community structure characterization[J]. Physical Review E, 2012, 85(2): 026109.
[2]Blondel V D, Guillaume J-L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
[3]Clauset A, Newman M E, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.
[4]Kelley S, Goldberg M, Magdon-Ismail M, et al. Defining and discovering communities in social networks[M]. Handbook of Optimization in Complex Networks. City: Springer, 2012: 139-168.
[5]Newman M E, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[6]Newman M E. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[7]Newman M E. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[8]Pons P, Latapy M. Computing communities in large networks using random walks[C] International symposium on computer and information sciences. Springer: 284-293.
[9]Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 036106.
[10]Reichardt J, Bornholdt S. Statistical mechanics of community detection[J]. Physical Review E, 2006, 74(1): 016110.
[11]Rosvall M, Bergstrom C T. Maps of Information Flow Reveal Community Structure In Complex Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008: 1118-1123.
[12]Rosvall M, Axelsson D, Bergstrom C T. The map equation[J]. The European Physical Journal Special Topics, 2009, 178(1): 13-23.
[13]Traag V A, Bruggeman J. Community detection in networks with positive and negative links[J]. Physical Review E, 2009, 80(3): 036115.
[14]Yang B, Liu D, Liu J. Discovering communities from social networks: Methodologies and applications[M]. Handbook of social network technologies and applications. City: Springer, 2010: 331-346.
[15]Yang J, Mcauley J, Leskovec J. Community detection in networks with node attributes[C] 2013 IEEE 13th International Conference on Data Mining. IEEE: 1151-1156.